In relational database management systems (relational DBMSs) data is stored in tables that have rows (records) and columns (fields or attributes). As data is added, deleted and modified in a relational database table, prior art DBMSs provide the user with the ability to rebuild the table. The reorganization or rebuilding of a table is desirable to permit the table to be efficiently accessed and updated by the relational DBMS. Reasons to reorganize a database table include improved clustering of data, reduction of pointers within the table, and improved distribution of free space in the table.
In prior art relational DBMSs, it is possible to reorganize a table offline. In its most simple form, users are denied access to the table during a potentially significant time while the table is being reorganized. This denial of access to the table is a significant cost to the long-term benefit of reorganizing the table.
A more sophisticated approach to table reorganization is to generate a shadow table that is a copy of the original table, reorganized for efficient accessing and updating. According to this prior art approach records are read from the original table and written to a new, shadow, table in a manner defined to provide a more efficiently organized shadow table. When the records have all been copied from the original table to the shadow table, the original table is replaced by the shadow table. An example of such an approach is set out in U.S. Pat. No. 5,721,915 (Sockut).
This prior art approach to database table reorganization requires significant data storage capability in the system of the DBMS as the data in the table is effectively duplicated during the building of the shadow table. The data in the table is also unavailable to users during the time that the original table is being replaced by the shadow table. A further shortcoming of this prior art approach is that the benefits of the reorganization of the data are not available to the user of the database table until the shadow table has replaced the original table.
Other prior art approaches involve the online reorganization of database tables. Zou, C. and Salzberg, B. describe certain online approaches in “Safely and Efficiently Updating References During On-Line Reorganization,” Proceedings of the 24th VLDB Conference, New York, U.S.A., 1998. In that paper, the reorganization of a database table is described in which records are moved in the database table, and indexes are updated while users are able to continue to access the database. In the Zou and Salzberg approach, locking protocols for table scanners are described. One locking solution described is to follow the level 3 consistency or repeatable read whereby all locks are kept until the end of a transaction and scanners lock with page or greater granularity (a scanner is a process which reads from an index or a data table, as is described in more detail below). A second approach outlined is to have each scanner lock on a latch which will prevent the reorganization from being carried out until the scanner releases the lock. However, such locking protocols significantly restrict the access to the database during the reorganization. Other algorithms are referred to in the Zou and Salzberg paper but those algorithms do not address the issues of concurrent reorganization and user access in a manner which is thought to be satisfactory for significant collections of data.
It is therefore desirable to reorganize relational tables so that the DBMS does not require significant data storage space for a shadow table, the table reorganization benefits are incrementally available to the user, and in which the user is able to access the data in the table during the table reorganization without observing significant reduction in performance of the DBMS.